目次
開催案内
耐量子計算機暗号に関するいくつかの研究事例
日時
2024年1月19日（金）16:45〜18:15
開催形式
対面(北部構内)とオンライン(Zoom)のハイブリッド
参加登録 https://forms.gle/qFp3G7WqyGYJGmt97
登録されたアドレスに教室の場所とZoomの接続情報を送付いたします。
講師
縫田 光司 氏（九州大学マス・フォア・インダストリ研究所 教授）
概要
量子計算機（量子コンピュータ）の研究開発が活発に行われる昨今、量子計算機をもってしても破れない（公開鍵）暗号技術である耐量子計算機暗号の重要性も増す一方である。今回は、耐量子計算機暗号の方式設計、方式の安全性検証、安全性仮定の妥当性検証にかかわるいくつかの研究事例を概説する。
備考
◎問い合わせ先：itami.masato.7u ＊ kyoto-u.ac.jp（＊を@に変えてください）
活動報告
九州大学の縫田光司さんに「耐量子計算機暗号に関するいくつかの研究事例」というタイトルで講演していただきました。
講演は耐量子計算機暗号が必要な理由の説明から始まりました。公開鍵暗号化通信や電子署名で現在利用されている方式は量子計算機によって危殆化してしまうため、量子アルゴリズムで破れない暗号技術の開発や、その計算量的安全性の評価が必要不可欠とのことでした。今回は耐量子計算機暗号に関する３つの研究事例について説明をしていただきました。
まず、耐量子計算機暗号の構成に関する研究事例として、署名方式UOVの改良について説明していだきました。署名方式UOVとは、有限体上の多変数2次多項式の求解がNP困難であることに基づく多変数多項式暗号の一種で、公開鍵が2次元の行列で表されるため鍵のサイズが大きいという欠点がありました。そのため、巡回行列を用いて鍵のサイズを減らしたBlock-Anti-Circulant UOVというものが考案されましたが、2020年に致命的な攻撃方法が見つかってしまったそうです。そこで、巡回行列を剰余環の元へ一般化することで攻撃を回避したQR-UOVが考案され、その中では新しい数学的事実の証明も行われたとのことでした。
次に、想定していたよりも安全性が低いことを明らかにした研究事例として、署名方式SPHINCS+の安全性解析について説明していただきました。SPHINCS+はハッシュベース署名の一種で、NIST標準にも選定されましたが、distinct-function multi-target second-preimage attackという攻撃方法が見つかり、SHA-256というハッシュ関数ベースの暗号の安全性が低下してしまったそうです。ただし、SHA-512を利用すれば安全性は高められるため、致命的な攻撃とはならなかったそうです。
最後に、耐量子計算機暗号の1つである格子暗号を攻撃するアルゴリズムの計算量を評価した研究事例として、LLL系格子基底簡約アルゴリズムの計算量評価について説明していただきました。格子の基底簡約とは、入力された格子の基底に対して、より短い基底を計算する操作で、その代表的な方法の1つがLLLアルゴリズムです。このアルゴリズムに含まれるパラメータδ(≦1)は大きいほど望ましい出力が得られますが、δ=1のときのみ計算量が多項式オーダーになることが示されていないそうです。そこでδ=1の場合に、ノルムがある値以下の格子点の数を次数に関して再帰的に評価することで、新たに得られた計算量の評価が紹介されました。しかし、この手法でも多項式オーダーであることは示せておらず、基本的なアルゴリズムでも研究すべきことはまだまだ残っているとのことでした。
講演中も講演後も多くの質問が出て、研究のアプローチの多様性や計算量の評価方法などに関して活発な議論が行われました。 （文責：伊丹將人）